package gold.enterprise;

import java.util.*;
import java.util.stream.Collectors;

/**
 * Created by fanzhenyu02 on 2021/12/27.
 */
public class Shengli_Amazon {

    public long startExecuteTime = System.currentTimeMillis();

    // good: 16

    public long findPasswordStrength(String password) {
        long count = 0;
        Map<Long, Long> prevCombinationRecord = new HashMap<>();
        Map<Long, Long> curCombinationRecord = new HashMap<>();

        for (int i = 0; i < password.length(); i++) {
            // 当前位置的单个字母可以直接算作一个组合情况，直接累计count
            ++count;
            curCombinationRecord.put(addOneCharToLong(0, password.charAt(i)), 1L);

            for (Long prevCombination : prevCombinationRecord.keySet()) {
                long addToPrevCombination = addOneCharToLong(prevCombination, password.charAt(i)), curAddBitCount = 0;
                if (prevCombinationRecord.containsKey(addToPrevCombination)) {
                    curAddBitCount = prevCombinationRecord.get(addToPrevCombination) + 1;
                } else {
                    curAddBitCount = bitCount(addToPrevCombination);
                }

                count += curAddBitCount;
                curCombinationRecord.put(addToPrevCombination, curAddBitCount);
            }

            // 王车易位
            Map<Long, Long> temp = prevCombinationRecord;
            temp.clear();
            prevCombinationRecord = curCombinationRecord;
            curCombinationRecord = temp;
        }

        return count;
    }

    /**
     * 此方法很玄妙，就是之前的结果只包含a-z这26个字母
     * 对应着0～25这26位的结果，可以用一个long型结果表示，当前位如果有则位1，无为0，对ch
     * 做按位或操作运算，得到下一位结果
     *
     * @param bit
     * @param ch
     * @return
     */
    public long addOneCharToLong(long bit, char ch) {
        long chBitNum = (1 << (ch - 'a'));
        return bit | chBitNum;
    }

    public long bitCount(long n) {
        long count = 0;
        while (n > 0) {
            n = n & (n - 1);
            count++;
        }
        return count;
    }

    public long findNth(int n) {
        TreeSet<Long> set = new TreeSet<>();
        long curTravel = 1L;
        set.add(curTravel);
        int counter = 0;
        while (counter <= n) {
            set.add(curTravel * 2 + 1);
            set.add(curTravel * 3 + 1);
            curTravel = set.higher(curTravel);
            ++counter;
        }

        return set.stream().collect(Collectors.toList()).get(n);
    }

    public long findNth_2Ver_Wrong_Thought(int n) {
        Set<Long> set = new HashSet<>();
        List<Long> numList = new LinkedList<>();

        int curTravelPointer = 0;
        set.add(1L);
        numList.add(1L);

        while (numList.size() <= n) {
            long curTravel = numList.get(curTravelPointer);

            if (!set.contains(curTravel * 2 + 1)) {
                set.add(curTravel * 2 + 1);
                numList.add(curTravel * 2 + 1);
            }

            if (!set.contains(curTravel * 3 + 1)) {
                set.add(curTravel * 3 + 1);
                numList.add(curTravel * 3 + 1);
            }

            ++curTravelPointer;
        }

        return set.stream().collect(Collectors.toList()).get(n);
    }

    public static void run() {
        Shengli_Amazon solution = new Shengli_Amazon();
//        System.out.println(solution.addOneCharToLong(6, 'd'));
//        System.out.println(solution.addOneCharToLong(0, 'c'));
//        System.out.println(solution.bitCount(1028L));
//        System.out.println(solution.findPasswordStrength("good"));
        System.out.println(solution.findNth_2Ver_Wrong_Thought(10));

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - solution.startExecuteTime) + " ms.");
    }

    public static void main(String[] args) {
        run();
    }

}

